#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int width = dungeon[0].size();
        int height = dungeon.size();
        vector<int> min_hp(width);
        min_hp[width - 1] = max(1, 1 - dungeon[height - 1][width - 1]);
        for (int i = width - 2; i >= 0; i--) {
            min_hp[i] = max(1, min_hp[i + 1] - dungeon[height - 1][i]);
        }
        for (int i = height - 2; i >= 0; i--) {
            min_hp[width - 1] -= dungeon[i][width - 1];
            min_hp[width - 1] = max(1, min_hp[width - 1]);
            for (int j = width - 2; j >= 0; j--) {
                min_hp[j] = min(min_hp[j] - dungeon[i][j], min_hp[j + 1] - dungeon[i][j]);
                min_hp[j] = max(1, min_hp[j]);
            }
        }
        return max(1, min_hp[0]);
    }
};

int main() {
    vector<vector<int>> input = {{1, -2, 3}, {2, -2, -2}};
    Solution solution;
    int output = solution.calculateMinimumHP(input);
    cout << output << endl;
    return 0;
}
